from typing import List
class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        res = []
        n = len(nums)
        def dfs(x):
            if x == n - 1:
                res.append(nums[:])
                return
            dic = set()
            for i in range(x, n):
                if nums[i] in dic: continue
                print(x, i, nums)
                dic.add(nums[i])
                print(dic)
                nums[i], nums[x] = nums[x], nums[i]
                dfs(x+1)
                nums[i], nums[x] = nums[x], nums[i]
        dfs(0)
        return res        

Solution().permuteUnique([1,1,2])